package com.wrial.simple;
/*
 * @Author  Wrial
 * @Date Created in 12:02 2020/3/31
 * @Description 编写一个程序，找到两个单链表相交的起始节点。
 */

public class LeetCode_160 {


    // 很妙的一种方法
    // 1.如果有一个链表是null，就返回null  2.如果连个链表是不等长度的，怎么让他们进行同步呢？
    // 因为两个链表的总长度是固定的，如果有相交的点一定会在遍历完两边后遇到
    // 如果此时a走完了，就去走b，b走完了就去走a，如果两个在中间有相同的节点就返回，否则不含重复部分
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) return null;
        ListNode pa = headA;
        ListNode pb = headB;
        while (pa != pb) {
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }
        return pa;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
